package org.apache.lucene.search;

/**
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

import java.io.IOException;
import java.util.ConcurrentModificationException;
import java.util.Vector;
import java.util.Iterator;

import org.apache.lucene.document.Document;
import org.apache.lucene.index.CorruptIndexException;

/**
 * A ranked list of documents, used to hold search results.
 * <p>
 * <b>Caution:</b> Iterate only over the hits needed. Iterating over all hits
 * is generally not desirable and may be the source of performance issues. If
 * you need to iterate over many or all hits, consider using the search method
 * that takes a {@link HitCollector}.
 * </p>
 * <p>
 * <b>Note:</b> Deleting matching documents concurrently with traversing the
 * hits, might, when deleting hits that were not yet retrieved, decrease
 * {@link #length()}. In such case,
 * {@link java.util.ConcurrentModificationException ConcurrentModificationException}
 * is thrown when accessing hit <code>n</code> &ge; current_{@link #length()}
 * (but <code>n</code> &lt; {@link #length()}_at_start).
 */
public final class Hits {
	private Weight weight;
	private Searcher searcher;
	private Filter filter = null;
	private Sort sort = null;

	private int length; // the total number of hits
	private Vector hitDocs = new Vector(); // cache of hits retrieved

	private HitDoc first; // head of LRU cache
	private HitDoc last; // tail of LRU cache
	private int numDocs = 0; // number cached
	private int maxDocs = 200; // max to cache

	private int nDeletions; // # deleted docs in the index.
	private int lengthAtStart; // this is the number apps usually count on
								// (although deletions can bring it down).
	private int nDeletedHits = 0; // # of already collected hits that were
									// meanwhile deleted.

	boolean debugCheckedForDeletions = false; // for test purposes.

	Hits(Searcher s, Query q, Filter f) throws IOException {
		weight = q.weight(s);
		searcher = s;
		filter = f;
		nDeletions = countDeletions(s);
		getMoreDocs(50); // retrieve 100 initially
		lengthAtStart = length;
	}

	Hits(Searcher s, Query q, Filter f, Sort o) throws IOException {
		weight = q.weight(s);
		searcher = s;
		filter = f;
		sort = o;
		nDeletions = countDeletions(s);
		getMoreDocs(50); // retrieve 100 initially
		lengthAtStart = length;
	}

	// count # deletions, return -1 if unknown.
	private int countDeletions(Searcher s) throws IOException {
		int cnt = -1;
		if (s instanceof IndexSearcher) {
			cnt = s.maxDoc() - ((IndexSearcher) s).getIndexReader().numDocs();
		}
		return cnt;
	}

	/**
	 * Tries to add new documents to hitDocs. Ensures that the hit numbered
	 * <code>min</code> has been retrieved.
	 */
	private final void getMoreDocs(int min) throws IOException {
		if (hitDocs.size() > min) {
			min = hitDocs.size();
		}

		int n = min * 2; // double # retrieved
		TopDocs topDocs = (sort == null) ? searcher.search(weight, filter, n)
				: searcher.search(weight, filter, n, sort);

		length = topDocs.totalHits;
		ScoreDoc[] scoreDocs = topDocs.scoreDocs;

		float scoreNorm = 1.0f;

		if (length > 0 && topDocs.getMaxScore() > 1.0f) {
			scoreNorm = 1.0f / topDocs.getMaxScore();
		}

		int start = hitDocs.size() - nDeletedHits;

		// any new deletions?
		int nDels2 = countDeletions(searcher);
		debugCheckedForDeletions = false;
		if (nDeletions < 0 || nDels2 > nDeletions) {
			// either we cannot count deletions, or some "previously valid hits"
			// might have been deleted, so find exact start point
			nDeletedHits = 0;
			debugCheckedForDeletions = true;
			int i2 = 0;
			for (int i1 = 0; i1 < hitDocs.size() && i2 < scoreDocs.length; i1++) {
				int id1 = ((HitDoc) hitDocs.get(i1)).id;
				int id2 = scoreDocs[i2].doc;
				if (id1 == id2) {
					i2++;
				} else {
					nDeletedHits++;
				}
			}
			start = i2;
		}

		int end = scoreDocs.length < length ? scoreDocs.length : length;
		length += nDeletedHits;
		for (int i = start; i < end; i++) {
			hitDocs.addElement(new HitDoc(scoreDocs[i].score * scoreNorm,
					scoreDocs[i].doc));
		}

		nDeletions = nDels2;
	}

	/** Returns the total number of hits available in this set. */
	public final int length() {
		return length;
	}

	/**
	 * Returns the stored fields of the n<sup>th</sup> document in this set.
	 * <p>
	 * Documents are cached, so that repeated requests for the same element may
	 * return the same Document object.
	 * 
	 * @throws CorruptIndexException
	 *             if the index is corrupt
	 * @throws IOException
	 *             if there is a low-level IO error
	 */
	public final Document doc(int n) throws CorruptIndexException, IOException {
		HitDoc hitDoc = hitDoc(n);

		// Update LRU cache of documents
		remove(hitDoc); // remove from list, if there
		addToFront(hitDoc); // add to front of list
		if (numDocs > maxDocs) { // if cache is full
			HitDoc oldLast = last;
			remove(last); // flush last
			oldLast.doc = null; // let doc get gc'd
		}

		if (hitDoc.doc == null) {
			hitDoc.doc = searcher.doc(hitDoc.id); // cache miss: read document
		}

		return hitDoc.doc;
	}

	/** Returns the score for the n<sup>th</sup> document in this set. */
	public final float score(int n) throws IOException {
		return hitDoc(n).score;
	}

	/**
	 * Returns the id for the n<sup>th</sup> document in this set. Note that
	 * ids may change when the index changes, so you cannot rely on the id to be
	 * stable.
	 */
	public final int id(int n) throws IOException {
		return hitDoc(n).id;
	}

	/**
	 * Returns a {@link HitIterator} to navigate the Hits. Each item returned
	 * from {@link Iterator#next()} is a {@link Hit}.
	 * <p>
	 * <b>Caution:</b> Iterate only over the hits needed. Iterating over all
	 * hits is generally not desirable and may be the source of performance
	 * issues. If you need to iterate over many or all hits, consider using a
	 * search method that takes a {@link HitCollector}.
	 * </p>
	 */
	public Iterator iterator() {
		return new HitIterator(this);
	}

	private final HitDoc hitDoc(int n) throws IOException {
		if (n >= lengthAtStart) {
			throw new IndexOutOfBoundsException("Not a valid hit number: " + n);
		}

		if (n >= hitDocs.size()) {
			getMoreDocs(n);
		}

		if (n >= length) {
			throw new ConcurrentModificationException(
					"Not a valid hit number: " + n);
		}

		return (HitDoc) hitDocs.elementAt(n);
	}

	private final void addToFront(HitDoc hitDoc) { // insert at front of cache
		if (first == null) {
			last = hitDoc;
		} else {
			first.prev = hitDoc;
		}

		hitDoc.next = first;
		first = hitDoc;
		hitDoc.prev = null;

		numDocs++;
	}

	private final void remove(HitDoc hitDoc) { // remove from cache
		if (hitDoc.doc == null) { // it's not in the list
			return; // abort
		}

		if (hitDoc.next == null) {
			last = hitDoc.prev;
		} else {
			hitDoc.next.prev = hitDoc.prev;
		}

		if (hitDoc.prev == null) {
			first = hitDoc.next;
		} else {
			hitDoc.prev.next = hitDoc.next;
		}

		numDocs--;
	}
}

final class HitDoc {
	float score;
	int id;
	Document doc = null;

	HitDoc next; // in doubly-linked cache
	HitDoc prev; // in doubly-linked cache

	HitDoc(float s, int i) {
		score = s;
		id = i;
	}
}
